class OneWayLinkNode{
    next = null;
    element = null;
    constructor(element){
        this.element = element;
    }
}
class OneWayLink{
    headNode = null;
    constructor(){}
    createNode(element){
        const node = new OneWayLinkNode(element);
        return node;
    }
    append(element){
        const node = this.createNode(element);
        let currentNode = this.headNode;
        if(currentNode){
            while(currentNode.next){
                currentNode = currentNode.next;
            }
            currentNode.next = node;
        }else{
            this.headNode = node;
        }
        return node;
    }
    search(element){
        let currentNode = this.headNode;
        if(!currentNode){
            return null;
        }
        while(currentNode){
            if(currentNode.element === element){
                return currentNode;
            }
            currentNode = currentNode.next;
        }
        return null;
    }
    insert(position, element){
        const node = this.createNode(element);
        let currentIndex = 0;
        let currentNode = this.headNode;
        if(!currentNode){
            this.headNode = node;
        }else if(position === 0){
            const oldHeadNode = this.headNode;
            this.headNode = node;
            node.next = oldHeadNode;
        }else{
            while(currentNode){
                if(position === currentIndex){
                    const nextNode = currentNode.next;
                    currentNode.next = node;
                    node.next = nextNode;
                    return node;
                }
                currentIndex++;
                if(currentIndex > position){
                    currentNode.next = node;
                    return node;
                }
                currentNode = currentNode.next;
            }
        }
        
    }
    remove(element){
        let prevNode = null;
        let currentNode = this.headNode;
        if(!currentNode){
            return null;
        }
        while(currentNode){
            if(currentNode.element === element){
                if(prevNode){
                    prevNode.next = currentNode.next;
                }else{
                    // 处理头节点的情况
                    this.headNode = currentNode.next;
                }
                return currentNode;
            }
            prevNode = currentNode;
            currentNode = currentNode.next
        }
        return null;
    }
}
class DoublyLinkNode{
    prev = null;
    next = null;
    element = null;
    constructor(element){
        this.element = element;
    }
}
class DoublyLink{
    head = null;
    tail = null;
    length = 0;
    insert(position, element){
        const node = new DoublyLinkNode(element);
        if(!this.head){
            this.head = node;
            this.tail = node;
        }else if(position == 0){
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        }else if(position >= this.length){
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }else if(position > 0){
            // 插入中间
            let currentNode = this.head;
            let index = 0;
            while(index < position){
                currentNode = currentNode.next;
                index++;
            }
            const oldNext = currentNode.next;
            node.prev = currentNode;
            node.next = oldNext;
            if(oldNext) {
                oldNext.prev = node;
            }
            currentNode.next = node;
        }else{
            return false;
        }
        this.length++;
        return true;
    }
    append(element){
        const node = new DoublyLinkNode(element);
        if(!this.tail){
            this.tail = node;
            this.head = node;
        }else{
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        this.length++;
    }
}